package com.sheyu;

import java.util.Arrays;
import java.util.Map;
import java.util.Stack;

/**
 * @author sheyu
 * @date 2020/8/26 9:50 上午
 */
public class Index_84 {
    /**
     * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
     *
     * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
     * 暴力求解
     *
     */
    public static int largestRectangleArea1(int[] heights) {
        int maxArea = 0;
        for (int i = 0; i < heights.length; i++) {
            int minValue = heights[i];
            for (int j = i; j < heights.length; j++) {
                if (heights[j]>minValue){
                    maxArea = Math.max(maxArea,minValue*(j-i+1));
                }else{
                    minValue = heights[j];
                    maxArea = Math.max(maxArea,minValue*(j-i+1));
                }
            }
        }
        return maxArea;
    }

    //获取左边第一个小于自己的数，构造一个单调递减栈
    private int[] getLeftMinNum(int[] src) {
        int[] result = new int[src.length];
        Stack<Integer> monotoneStack = new Stack<>();
        for (int i = 0; i < src.length; i++) {
            if (monotoneStack.isEmpty()) {
                monotoneStack.push(src[i]);
                result[i] = 0;
            } else {
                while (!monotoneStack.isEmpty() && src[i] < monotoneStack.peek()) {
                    monotoneStack.pop();
                }
                if (!monotoneStack.isEmpty()) {
                    result[i] = monotoneStack.peek();
                } else {
                    result[i] = -1;
                }
                monotoneStack.push(src[i]);
            }
        }
        return result;
    }

    /*
     * 本伪代码对应的是单调递减栈
     *共n个元素，编号为0~n-1

    while(栈为空) 栈顶元素出栈; //先清空栈
        a[n]=-1;
    for(i=0;i<=n;i++)
        {
            if(栈为空或入栈元素大于等于栈顶元素) 入栈;
            else
            {
                while(栈非空并且栈顶元素大于等于入栈元素)
                {
                    栈顶元素出栈;
                    更新结果;
                }
                将最后一次出栈的栈顶元素（即当前元素可以拓展到的位置）入栈;
                更新最后一次出栈的栈顶元素其对应的值;
            }
        }
        输出结果;
        */

    /**
     * 思路：取右边的最小边界，即left数组，取左边的最小边界，即right数组
     * @param heights
     * @return
     */
    public static int largestRectangleAreaMin(int[] heights) {
        int maxArea = 0;
        int nLength = heights.length;
        Stack<Integer> stack = new Stack<>();
        int[] left = new int[heights.length];
        int[] right = new int[heights.length];
        for (int i = 0; i < nLength; i++) {
            while(!stack.isEmpty()&&heights[stack.peek()]>=heights[i]){
                stack.pop();
            }
            left[i] = stack.size()==0?-1:stack.peek();
            stack.push(i);
        }
        stack.clear();
        for (int i = nLength-1; i >= 0; i--) {
            while(!stack.isEmpty()&&heights[stack.peek()]>=heights[i]){
                stack.pop();
            }
            right[i] = stack.size()==0?nLength:stack.peek();
            stack.push(i);
        }
        for (int i = 0; i < nLength; i++) {
            maxArea = Math.max(maxArea,(right[i]-left[i]-1)*heights[i]);
        }
        return maxArea;
    }
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int[] left = new int[n];
        int[] right = new int[n];
        Arrays.fill(right, n);

        Stack<Integer> mono_stack = new Stack<Integer>();
        for (int i = 0; i < n; ++i) {
            while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
                right[mono_stack.peek()] = i;
                mono_stack.pop();
            }
            left[i] = (mono_stack.isEmpty() ? -1 : mono_stack.peek());
            mono_stack.push(i);
        }

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);
        }
        return ans;
    }
    public static void main(String[] args) {
        int[]heights = new int[]{2,1,1,1,1,2};
        System.out.println(largestRectangleAreaMin(heights));
    }

}
